


class Solution:
    def mao_gai(self,target):
        for i in range(len(target)-1):
            for j in range(i,len(target)):
                if target[i] > target[j]:
                    target[i],target[j] = target[j],target[i]
        return target


    def mao_yuan(self,target):
        for i in range(len(target)):
            for j in range(len(target)-i-1):
                if target[j] > target[j+1]:
                    target[j+1], target[j] = target[j], target[j+1]


text = [4,5,7,1,5,3,9,4,6]










class QuickSort2:
    def __init__(self):
        pass
    # 此函数完成分区操作
    def partition(self,arr, left, right):
        key = left  # 划分参考数索引,默认为第一个数为基准数，可优化
        while left < right:
            # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
            while left < right and arr[right] >= arr[key]:
                right -= 1
            # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现
            while left < right and arr[left] <= arr[key]:
                left += 1
            # 此时已找到一个比基准大的书，和一个比基准小的数，将他们互换位置
            arr[left], arr[right] = arr[right], arr[left]

        # 当从两边分别逼近，直到两个位置相等时结束，将左边小的同基准进行交换
        arr[left], arr[key] = arr[key], arr[left]
        # 返回目前基准所在位置的索引
        return left

    def quicksort(self,arr, left, right):
        if left >= right:
            return
        # 从基准开始分区
        mid = self.partition(arr, left, right)
        # 递归调用
        # print(arr)
        self.quicksort(arr, left, mid - 1)
        self.quicksort(arr, mid + 1, right)

    def run(self,lst):
        n = len(lst)
        if n <= 1:
            return lst
        self.quicksort(lst, 0, n - 1)
        return lst



class A:
    def __init__(self):
        pass

    def p(self,ary,left,right):
        key = left
        while left< right:
            while left < right and ary[left] <= ary[key]:
                left += 1
            while left< right and ary[right]>= ary[key]:
                right -= 1

            ary[left],ary[right] =ary[right],ary[left]
        ary[key],ary[left] =ary[left] ,ary[key]
        return left

    def q(self,ary,left,right):
        if left >= right:
            return
        mid = self.p(ary,left,right)
        self.p(ary,left,mid-1)
        self.p(ary,mid+1,right)


    def run(self,ary):
        n = len(ary)
        if n <=1:
            return ary
        self.q(ary,0,n-1)
        return ary


def b(ary,start,end):
    if start >= end:
        return
    mid = ary[start]
    left = start
    right = end
    while left < right:
        while left < right and ary[right] >= mid:
            right -= 1
        ary[left] = ary[right]
        while left < right and ary[left] <= mid:
            left += 1
        ary[right] = ary[left]
    ary[left] = mid
    #这里注意是left -1 的坐标，因为mid
    b(ary,start,left-1)
    b(ary,left+1,end)







if __name__ == '__main__':
    # S= Solution()
    # S.mao_yuan(text)

    # Q = Quick()
    # print(Q.run(text))
    # Q = QuickSort(text)
    # print(Q)
    # Q = QuickSort2()
    # print(Q.run(text))
    # a = A()
    # a.run(text)
    b(text,0,len(text)-1)
    # quick_sort(text,0,len(text)-1)
    print(text)